In computer programming, it is often convenient to refer to a plurality of data objects as a group, or array. An array's size may be assigned at the outset, and a block of memory space suitable for containing an array of that size is allocated. The array may be allocated statically (e.g., when the program is initially loaded) or dynamically (e.g., at a point in the program's execution at which it is determined that the array will be needed). Even though the program allocates the array dynamically, the array's size may be fixed when that allocation occurs. Contiguous memory locations may be allocated for the array.
Contiguous allocation of large arrays, however, may be problematic. For example, if the array sizes vary over the lifetime of a process, fragmentation issues may arise.
Additionally, it may be inconvenient to restrict arrays to fixed sizes. The array's ultimate needed size may be unknown but potentially very large when the array is initially allocated, and it may be wasteful to initially allocate the maximum possible array size. A traditional solution to this problem is determining that the array includes more elements than the memory so far allocated to it can hold and then allocating space twice as large as the array's previous space. The current content is copied into the new space's first half, and then new elements are added to the new space's second half, possibly initializing the second-half contents in the process. Pointers to the array are then adjusted to refer to the array's new location. This approach has become popular because it enables the program to avoid allocating space of the maximum size when an array that may never grow to that size is initially allocated. But it also has certain disadvantages, such as wasted memory space.
Further, a persistent data structure may refer to a data structure that preserves the previous version of itself when it is modified. Persistent data structures are particularly common in logical and functional programming. Such a data structure is effectively immutable, as its operations do not (visibly) update the structure in-place, but instead yields a new updated structure. A data structure that is partially persistent may refer to a data structure that has all versions of the data structure accessible but only the newest version of the data structure is modifiable. A data structure that is fully persistent may refer to a data structure that has all versions of the data structure both accessible and modifiable. While persistence can be achieved by simple copying and modifying the data structure, this may be inefficient in terms of CPU (central processing unit) and RAM (random access memory) usage.
Moreover, the computer executing a program may allocate memory for objects from a free memory area called a heap. Memory is allocated to, and freed from, the heap in blocks. Eventually, when the objects are no longer being referenced by the program, the memory allocated for the created objects is reclaimed through a garbage collection process. Garbage collection may refer to a process of identifying unused areas of main memory storage. The garbage collection process clears the objects from memory whereby the once allocated memory is again available for use. Allocating memory for persistent data structures may be challenging because a persistent data structure preserves the previous version of itself when it is modified.